package de.infotheo;

/* bigfactor implements prime factoring for arbitrary-precision
numbers using Java 1.1+ BigInteger class 
                                   M. Gallant  10/09/2000       */

import java.util.*;
import java.math.BigInteger;

public class BigPrimeFactor {
static final BigInteger zero = new BigInteger("0") ;
static final BigInteger one = new BigInteger("1") ;
static final BigInteger two = new BigInteger("2") ;
static final BigInteger three = new BigInteger("3") ;

 public static void main(String args[]) {
	BigPrimeFactor bpf = new BigPrimeFactor() ;
     for (int i = 0; i < args.length; i++)
		System.out.println(bpf.getPrimeFactors(args[i])+"\r\n") ;
 }


public String getPrimeFactors(String stringnumber) {
	StringBuffer strbuf = new StringBuffer() ;
         try {
             BigInteger number = new BigInteger(stringnumber);
               if (number.compareTo(zero) <= 0)
                return("***** Select a number >1 *****");
             strbuf.append("isProbablePrime  (10^12:1)  " + number.isProbablePrime(40)+"\r\n\r\n");
             strbuf.append(number + " = ");
             Vector factors = getFactors(number);
             for (int j = 0; j < factors.size(); j++) {
                 if (j != 0)
                     strbuf.append(" * ");
                 strbuf.append("" + (BigInteger) factors.elementAt(j));
             }
             strbuf.append("\r\n");
             strbuf.append(verifyFactors(number, factors)) ;
         }
	 catch (NumberFormatException e) {
		strbuf.append("***** Not a number! *****") ;
           }
  return strbuf.toString() ;
}

private Vector getFactors(BigInteger number) { // number should be positive
     Vector factors = new Vector();

     while (number.mod(two).compareTo(zero) == 0) {
           // System.out.println("New factor: " + two) ;
         number=number.divide(two);
         factors.addElement(two);
     }

     BigInteger limit = bigRoot(number).add(one);
       // System.out.println("Initial search limit: " + limit) ;
factor:
     for (BigInteger i = three; i.compareTo(limit) <= 0; i=i.add(two)) {
         while (number.mod(i).compareTo(zero) == 0) {
               // System.out.println("New factor: " + i) ;
             number=number.divide(i) ;
             factors.addElement(i);
             if (number.compareTo(one) == 0)
                 break factor;
             limit = bigRoot(number).add(one);
         }
     }

     if (number.compareTo(one) != 0 || factors.size() == 0)
         factors.addElement(number);

     return factors;
 }


public BigInteger bigRoot(BigInteger number) {
 BigInteger result = zero ;
 BigInteger oldRoot ;
 BigInteger newRoot ;
 BigInteger zero=new BigInteger("0") ;
 BigInteger two =new BigInteger("2") ;

 BigInteger num = number ; 
 newRoot = num.shiftRight(num.bitLength()/2) ;
 do {
  oldRoot = newRoot ;
  newRoot = oldRoot.multiply(oldRoot).add(num).divide(oldRoot).divide(two) ;
 } while(newRoot.subtract(oldRoot).abs().compareTo(two)>0) ;

 return newRoot;
}


private String verifyFactors(BigInteger number, Vector factors) {
       String status = "" ;
       BigInteger check = one;  //initialize check product of factors.
        for(int k = 0; k < factors.size() ; k++) 
          check = check.multiply((BigInteger) factors.elementAt(k)) ;
        if(check.compareTo(number) ==0)
          status = "Factor Verification OK ---------" ;
         else
          status = "!!!!! Problem with verifying product of factors !!!!!";
      return status ;
}


}
